<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>算法实验一</title>
    <script>
        // function maxSum(arr) {
        //     var current = 0,
        //         sum = 0;
        //     for (var i = 0; i < arr.length; i++) {
        //         if (current > 0) {
        //             current += arr[i];
        //         } else {
        //             current = arr[i];
        //         }
        //         if (current > sum) {
        //             sum = current;
        //         }
        //     }
        //     return sum;
        // }
        // console.log(maxSum([1, 2, -1, 3, -8, -4])); // 5
<!--        var array=[1, 2, -1, 3, -8, -4];-->
<!--        var b=0;-->
<!--        var sum=0;-->
<!--        for(var i=0;i<array.length;i++)-->
<!--        {-->
<!--            if(b>0)-->
<!--            {-->
<!--                b+=array[i];-->
<!--                document.write(b+";"+array[i]+"<br/>");-->
<!--            }-->
<!--            else-->
<!--            {-->
<!--                b=array[i];-->
<!--            }-->
<!--            if(b>sum)-->
<!--            {-->
<!--                sum=b;-->
<!--                document.write("sum:"+sum+"<br/>");-->
<!--            }-->
<!--        }-->
<!--        document.write(sum);-->
    </script>
</head>
<body>
    <div class="content">
            内容：[1, 2, -1, 3, -8, -4]
        <br><br/>
            预期答案：5
    </div>
    <div>
        得到答案：
        <script>
            function maxsum(arr, left, right){
                var sum=0;
                var center, leftsum, rightsum,s1,lefts,i,s2,rights,j;
                if (left==right)        //如果序列长度为1，直接求解
                {
                    if (arr[left]>0)
                        sum=arr[left];
                    else
                        sum=0;
                }
                else
                {
                    center=Math.floor((left+right)/2);    //划分
                    leftsum=maxsum(arr, left, center);
                    //对应情况①，递归求解
                    rightsum=maxsum(arr, center+1, right);
                    //对应情况②，递归求解
                    s1=0;
                    lefts=0;
                    //以下对应情况③，先求解s1
                    for (i=center; i>=left; i--)
                    {
                        lefts+=arr[i];
                        if (lefts>s1){
                            s1=lefts;
                        }
                    }
                    s2=0;
                    rights=0;             //再求解s2
                    for (j=center+1; j<=right; j++)
                    {
                        rights+=arr[j];
                        if (rights>s2){
                            s2=rights;
                        }
                    }
                    sum=s1+s2;              //计算情况③的最大子段和
                    if (sum<leftsum){
                        sum=leftsum;
                    }
                    //合并，在sum、leftsum和rightsum中取较大者
                    if (sum<rightsum){
                        sum=rightsum;
                    }
                }
                return sum;
            }
            var array=[1, 2, -1, 3, -8, -4];
            // var b=0;
            // var sum=0;
            // for(var i=0;i<array.length;i++)
            // {
            //     if(b>0)
            //     {
            //         b+=array[i];
            //     }
            //     else
            //     {
            //         b=array[i];
            //     }
            //     if(b>sum)
            //     {
            //         sum=b;
            //     }
            // }
            var sum;
            sum=maxsum(array, 0, 5);
            document.write(sum);
        </script>
    </div>
</body>
</html>